package leetcode_900;

import java.util.Arrays;

/**
 *@author 周杨
 *SumOfSubsequenceWidths_891  给定一个数组 问其子序列的 最大值和最小值的差值的sum和
 *describe:用动态规划 是数学问题 AC 13%
 *2018年11月12日 上午9:47:50
 */
public class SumOfSubsequenceWidths_891 {
	 public int sumSubseqWidths(int[] A) {
		 long help[]=new long[A.length];
	     int MOD=1000000007;
	     long res=0;
	     Arrays.sort(A);//排序
	     help[0]=1;
	     for(int i=1;i<A.length;++i) {//构造help[]数组
	    	 //对于任何A[i] 总有2 ^ i 以A[i]为最大值
	    	 help[i]=(help[i-1]*2+MOD)%MOD;
	     }
	     for(int i=0;i<A.length;++i) {
	    	 //对于任何A[i] 总有 n - i - 1 个更大的数
	    	 // 2 ^ (n - i - 1)个子序列 是以A[i]最小
	    	 res=(res+A[i]*(help[i]-help[A.length-1-i]))%MOD;
	     }
	     return (int) (res%MOD);
	 }
}
